import functools


class Solution(object):
    def makesquare(self, matchsticks):
        """
        :type matchsticks: List[int]
        :rtype: bool
        """
        n = len(matchsticks)
        if n <= 3:
            return False
        total = sum(matchsticks)
        if total % 4 != 0:
            return False
        target = total // 4
        if max(matchsticks) > target:
            return False

        @functools.cache
        def search(value, k):
            if k == 3:
                return True
            t = n - 1
            while t >= 0:
                if value >> t & 1:
                    break
                else:
                    t -= 1
            now_v = value - (1 << t)
            now_c = matchsticks[t]
            if now_c == target:
                return search(now_v, k + 1)
            else:
                d = {now_v: now_c}
                t -= 1
                while t >= 0:
                    next_d = {}
                    for key in d:
                        next_d[key] = d[key]
                        if key >> t & 1:
                            next_v = key - (1 << t)
                            next_c = d[key] + matchsticks[t]
                            if next_c == target:
                                flag = search(next_v, k + 1)
                                if flag:
                                    return True
                            else:
                                if next_c < target:
                                    next_d[next_v] = next_c
                    d = next_d
                    t -= 1
                return False

        return search(2 ** n - 1, 0)


data = Solution()
matchsticks = [1, 2, 3, 4, 5, 6, 7, 8, 9]
print(data.makesquare(matchsticks))
